App.require(function () {
    function BarneshutTree(nodes, width, height) {
        this.nodes = nodes;
        this.width = width;
        this.height = height;
        this.maxLength = 10;
    }
    BarneshutTree.prototype = {
        constructor: BarneshutTree,
        create: function () {
            var nodes = this.nodes, width = this.width, height = this.height;
            this.tree = { type: "treeNode", len : 1 };
    
            for (var i = 0; i < nodes.length; i++) {
                this.createNode(0, 0, width, height, this.tree, nodes[i]);
            }
            this.calculateMass(this.tree);
        },
        calculateNodeMass: function (treeNode) {
            if (treeNode.type === "treeNode") return this.calculateMass(treeNode);
            else {  
                if (Array.isArray(treeNode)) {
                    treeNode.mass = 0;
                    for (var i = 0; i < treeNode.length; i++) {
                        treeNode[i].mass = treeNode[i].mass || 1;
                        treeNode.mass += treeNode[i].mass;
                    }
                }
                else {
                    treeNode.mass = treeNode.tree || 1;
                }
                
                return treeNode.mass;
            }
        },
        calculateMass: function (tree) {
            var mass = 0;
            if (tree.leftTopNode) mass += this.calculateNodeMass(tree.leftTopNode);
            if (tree.leftBottomNode) mass += this.calculateNodeMass(tree.leftBottomNode);
            if (tree.rightTopNode) mass += this.calculateNodeMass(tree.rightTopNode);
            if (tree.rightBottomNode) mass += this.calculateNodeMass(tree.rightBottomNode);
            tree.mass = mass;
            return mass;
        },
        createTreeNode: function (x, y, w, h, obj, str, node) {
            if (obj[str]) {
                if (obj[str].type === "treeNode") {
                    this.createNode(x, y, w, h, obj[str], node);
                }
                else {
                    var node1 = obj[str];
                    if (obj.len < this.maxLength) {
                        obj[str] = { len: obj.len + 1, type: "treeNode", cx: x + w / 2, cy: y + h / 2, x: x, y: y, w: w, h: h };
                        this.createNode(x, y, w, h, obj[str], node1);
                        this.createNode(x, y, w, h, obj[str], node);
                    }
                    else {
                        if (Array.isArray(node1)) {
                            node1.push(node);
                        }
                        else {
                            obj[str] = [node1, node];
                        }
                    }
                }
            }
            else {
                obj[str] = node;
            }
        },
        createNode: function (x, y, w, h, obj, node) {
            if (node.x < (x + w / 2)) {
                if (node.y < (y + h / 2)) this.createTreeNode(x, y, w / 2, h / 2, obj, "leftTopNode", node);
                else this.createTreeNode(x, y + h / 2, w / 2, h / 2, obj, "leftBottomNode", node);
            }
            else {
                if (node.y < (y + h / 2)) this.createTreeNode(x + w / 2, y, w / 2, h / 2, obj, "rightTopNode", node);
                else this.createTreeNode(x + w / 2, y + h / 2, w / 2, h / 2, obj, "rightBottomNode", node);
            }
        },
        reset: function (width, height) {
            this.width = width;
            this.height = height;
            this.create();
        }
    }

    function KP(nodes, edges, width, height, obj) {
        this.nodes = nodes;
        this.edges = edges;
        this.width = width;
        this.height = height;
        this.initPosition(nodes);
        if (obj.calcposition == "auto") {
            this.tree = new BarneshutTree(nodes, width, height);
        }
        this.constant = obj.constant || 20000;
        this.hkConstant = obj.hk || 0.3;
        this.maxLength = obj.edgelength || 60;
        this.maxStep = 150;
        this.nodeMap = {};
        for (var i = 0; i < nodes.length; i++) {
            this.nodeMap[nodes[i].id] = nodes[i];
        }
        
        this.step = 0;
        this.showId = null;
    }
    KP.prototype = {
        constructor: KP,
        initPosition: function (nodes) {
            var width = this.width, height = this.height;
            var center = { x: width / 2, y: height / 2 };
            var r = Math.min(width, height) / 2 - 20;
            var needCNodes = nodes.filter(function (item) {
                var isFilter = !(item.x && item.y);
                item.x = parseFloat(item.x);
                item.y = parseFloat(item.y);
                return isFilter;
            })
            for (var i = 0; i < needCNodes.length; i++) {
                var theta = i / needCNodes.length * Math.PI * 2;
                if (!needCNodes[i].x) needCNodes[i].x = center.x + r * Math.cos(theta);
                else needCNodes[i].x = parseFloat(needCNodes[i].x);
                if (!needCNodes[i].y) needCNodes[i].y = center.y + r * Math.sin(theta);
                else needCNodes[i].y = parseFloat(needCNodes[i].y);
            }
        },
        computedPosition: function () {
            if (!this.tree) return;
            for (var i = 0; i < this.maxStep; i++) {
                this.update();
            }
            var nodes = this.nodes, cp = { x: 0, y: 0 }, len = nodes.length;
            for (var i = 0; i < len; i++) {
                cp.x += nodes[i].x;
                cp.y += nodes[i].y;
            }
            cp.x /= len;
            cp.y /= len;
            var deltaX = cp.x - this.width / 2, deltaY = cp.y - this.height / 2;
            for (var i = 0; i < len; i++) {
                nodes[i].x -= deltaX;
                nodes[i].y -= deltaY;
            }
        },
        update: function () {
            this.step++;
            if (this.step > this.maxStep) return cancelAnimationFrame(this.showId);
            this.tree.create();
            var tree = this.tree.tree, nodes = this.nodes, edges = this.edges;
            for (var i = 0; i < nodes.length; i++) {
                nodes[i].force = this.computeTreeForce(nodes[i], tree);
            }
            for (var i = 0; i < edges.length; i++) {
                this.computeEdgeForce(edges[i]);
            }
    
            for (var i = 0; i < nodes.length; i++) {
                nodes[i].x += nodes[i].force.x * (this.maxStep - this.step) / this.maxStep;
                nodes[i].y += nodes[i].force.y * (this.maxStep - this.step) / this.maxStep;
                if (nodes[i].x < 0) nodes[i].x = 10;
                if (nodes[i].x > this.width) nodes[i].x = this.width - 10;
                if (nodes[i].y < 0) nodes[i].y = 10;
                if (nodes[i].y > this.height) nodes[i].y = this.height - 10;
                nodes[i].force = { x: 0, y: 0 };
            }
        },
        computeTreeForce: function (node, tree, force) {
            force = force || { x: 0, y: 0 };
    
            if (tree.type === "treeNode") {
                this._calcuteTreeNodeForce(node, tree.leftTopNode, force);
                this._calcuteTreeNodeForce(node, tree.leftBottomNode, force);
                this._calcuteTreeNodeForce(node, tree.rightTopNode, force);
                this._calcuteTreeNodeForce(node, tree.rightBottomNode, force);
            }
            else {
                if (Array.isArray(tree)) {
                    for (var i = 0; i < tree.length; i++) {
                        this.computeNodesForce(node, tree[i], force);
                    }
                }
                else {
                    this.computeNodesForce(node, tree, force);
                }
            }
    
            return force;
        },
        computeNodesForce: function (node1, node2, force) {
            if (node1 === node2) return;
            var vector = { x: node1.x - node2.x, y: node1.y - node2.y };
            var sqrtDist = vector.x * vector.x + vector.y * vector.y;
            if (sqrtDist < 400) {
                sqrtDist = 400;
                node1.x -= 10;
                node2.x += 10;
            }
            var dist = Math.sqrt(sqrtDist);
            vector.x /= dist;
            vector.y /= dist;
    
            var nForce = node1.mass * node2.mass * this.constant / sqrtDist;
            force.x += vector.x * nForce;
            force.y += vector.y * nForce;
        },
        addTreeForce: function (node, tree, force) {
            this.computeNodesForce(node, {
                x: tree.cx, y: tree.cy, mass: tree.mass
            }, force);
        },
        _calcuteTreeNodeForce: function (node, tree, force) {
            if (typeof tree === "undefined") return;
            if (tree.type === "treeNode") {
                if (KP.isNodeInTree(node, tree)) {
                    this.computeTreeForce(node, tree, force);
                }
                else {
                    this.addTreeForce(node, tree, force);
                }
            }
            else {
                if (Array.isArray(tree)) {
                    for (var i = 0; i < tree.length; i++) {
                        this.computeNodesForce(node, tree[i], force);
                    }
                }
                else {
                    this.computeNodesForce(node, tree, force);
                }
            }
        },
        computeEdgeForce: function (edge) {
            var fNode = this.nodeMap[edge.from], tNode = this.nodeMap[edge.to];
            if (fNode === tNode) return;
            var vector = { x: fNode.x - tNode.x, y: fNode.y - tNode.y };
            var sqrtDist = vector.x * vector.x + vector.y * vector.y;
            if (sqrtDist < 400) {
                sqrtDist = 400;
                fNode.x -= 10;
                tNode.x += 10;
            }
            var dist = Math.sqrt(sqrtDist);
            vector.x /= dist;
            vector.y /= dist;
            var force = Math.abs(this.maxLength - dist) * this.hkConstant;
            var forceVec = { x: vector.x * force, y: vector.y * force };
            if (dist > this.maxLength) {
                fNode.force.x -= forceVec.x;
                fNode.force.y -= forceVec.y;
                tNode.force.x += forceVec.x;
                tNode.force.y += forceVec.y;
            }
            else {
                fNode.force.x += forceVec.x;
                fNode.force.y += forceVec.y;
                tNode.force.x -= forceVec.x;
                tNode.force.y -= forceVec.y;
            }
        }
    }
    
    KP.isNodeInTree = function (node, tree) {
        var x = node.x, y = node.y;
        if (x < tree.x || x > tree.x + tree.w || y > tree.y + tree.h || y < tree.y) {
            return false;
        }
        return true;
    };
    
    App.define("relativeTool", { KP: KP, BarneshutTree: BarneshutTree });
});